/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2022-09-28
 * Time:23:11
 */

/**
 * 力扣剑指offer04:二维数组的查找
 */

public class findNumberIn2DArray {
    /**
     * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //二分查找
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;//列长
        int n = matrix[0].length;//行长
        for (int i = 0; i < n; i++) {
            int l = 0;
            int r = m - 1;
            while (l < r) {
                //二分查找
                int mid = (l + r + 1) >> 1;
                if (matrix[mid][i] <= target) {
                    l = mid;
                }else {
                    r = mid - 1;
                }
            }
            if (matrix[r][i] == target) {
                return true;
            }
        }
        return false;
    }
}
